有一栋高N层的楼，这栋楼里有个秘密实验室在B层，所以每次他移动的时候就有了一个限制，x为当前所在层，y为目标层，|x - y| < |x - b|。问说移动K次后，有多少不同的路径。
经过分析可得出他移动的层数一定在b的同侧，dp[i][j]表示第i次坐电梯，距离b最小值为j的路径总数，那么可以得到状态转移方程：
dp[i][j]=dp[i][j+1]+dp[i-1][j+1];//距离为j的可由距离大于j的所有位置得到。
if(j>2)dp[i][j]+=dp[i-1][(j+2)/2]-dp[i-1][j];//当j大于2时，还可由小于2的距离大于1/2 j小于 j的位置得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| long long dp[5003][5003];
int main()
{
int n,a,b,k;
scanf("%d%d%d%d",&n,&a,&b,&k);
if(a>b)
{
b=n-b+1;
a=n-a+1;
}
dp[0][b-a]=1;
for(int i=b-a-1;i>=1;i--)
dp[0][i]=dp[0][i+1];
for(int i=1;i<=k;i++)
for(int j=b-1;j>=1;j--)
{
dp[i][j]=dp[i][j+1]+dp[i-1][j+1];
if(j>2)dp[i][j]+=dp[i-1][(j+2)/2]-dp[i-1][j];
dp[i][j]=(dp[i][j]%mod+mod)%mod;
}
printf("%d\n",dp[k][1]);
}
|
EOF